class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        int a = 0, c = nums.size() - 1;
        int b = c - 1;
        for (c = nums.size() - 1; c >= 2;)
        {
            int temc = nums[c];
            a = 0;
            b = c - 1;
            while (a < b)
            {
                int target = -nums[c];
                if (nums[a] + nums[b] < target)
                {
                    a++;
                }
                else if (nums[a] + nums[b] == target)
                {
                    vector<int> tem = {nums[a], nums[b], nums[c]};
                    ans.push_back(tem);
                    int tema = nums[a];
                    int temb = nums[b];
                    //第一步去重 在固定c的情况下保证a b不相同
                    while (a < b && nums[a] == tema)
                        a++;
                    while (a < b && nums[b] == temb)
                        b--;
                }
                else
                {
                    b--;
                }
            }
            //第二步去重 防止c相同 a b也相同的情况
            while (c >= 2 && nums[c] == temc)
                c--;
        }
        return ans;
    }
};